package com.liufei.class08;

import com.liufei.class02.Code03_Comp;

import java.util.Arrays;

public class Code02_mergeSort {


    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }


    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        // 注意 L + (R - L) >> 1; 不对，这样写 L + ((R - L) >> 1) 才对
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }


    public static void merge(int[] arr, int L, int M, int R) {
        int[] newArr = new int[R - L + 1];
        int LIndex = L;
        int MIndex = M + 1;
        int index = 0;
        while (LIndex <= M && MIndex <= R) {
            if (arr[LIndex] <= arr[MIndex]) {
                newArr[index++] = arr[LIndex++];
            } else {
                newArr[index++] = arr[MIndex++];
            }
        }
        while (LIndex <= M) {
            newArr[index++] = arr[LIndex++];
        }
        while (MIndex <= R) {
            newArr[index++] = arr[MIndex++];
        }
        System.arraycopy(newArr, 0, arr, L, newArr.length);
    }

    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int N = arr.length;
        while (step < N) {
            int L = 0;
            while (L < N) {
                // int M = L + step - 1; 这里也有可能溢出，所以要判断下
                int M = 0;
                if (N - L < step) {
                    // 说明越界了
                    M = N - 1;
                } else {
                    M = L + step - 1;
                }
                if (M == N - 1) {
                    break;
                }
                // int R = L + step; 也有可能越界
                int R = 0;
                if (M > (N - step - 1)) {
                    // 越界了
                    R = N - 1;
                } else {
                    R = M + step;
                }
                merge(arr, L, M , R);
                // 最后 L 来到 R + 1的位置
                // 注意 L = R + 1也有可能越界
                if (R == N - 1) {
                    break;
                } else {
                    L = R + 1;
                }
            }
            // 这里不能直接 step *= 2，需要判断有没有越界
            // 这里不能 step >= (N / 2)。因为 N / 2是向下取整。比如 N = 17，17 / 2 = 8，
            // 当 step 等于8的时候，2 * 8 = 16, 是没有越界的
            if (step > (N / 2)) {
                break;
            } else {
                step *= 2;
            }
        }
        process(arr, 0, arr.length - 1);
    }





    public static boolean compare(int[] arr1, int[] arr2) {
        int L = arr1.length;
        for (int i = 0; i < L; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxLength = 1000;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = Code03_Comp.lenRandomValueRandom(maxLength, maxValue);
            int[] arr2 = new int[arr1.length];
            System.arraycopy(arr1, 0, arr2, 0, arr2.length);
            mergeSort(arr1);
            mergeSort2(arr2);
            //Arrays.sort(arr2);
            if (!compare(arr1, arr2)) {
                System.out.println("Oops!");
                System.out.println(arr1);
                System.out.println(arr2);
                return;
            }
        }
        System.out.println("测试结束");
    }
}
